// 数组中有2种数出现了奇数次，其他的数都出现了偶数次
// 返回这2种出现了奇数次的数
// 测试链接 : https://leetcode.cn/problems/single-number-iii/
public class Code05_DoubleNumber {
    public static int[] singleNumber(int[] nums) {
        // 1. 首先计算所有数的异或结果eor1
        int eor1 = 0;
        for (int num : nums) {
            // nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
            // 根据异或操作的性质，相同的数异或为0，偶数次异或结果也为0
            // 所以最终eor1的值为出现奇数次的两个数a和b的异或结果，即eor1 = a ^ b
            eor1 ^= num;
        }

        // 2. 利用Brian Kernighan算法提取eor1二进制里最右侧的1
        // 这个最右侧的1是a和b在某一位上不同的体现
        int rightOne = eor1 & (-eor1);

        // 3. 再次遍历数组nums，根据元素与rightOne的按位与结果进行分组异或
        int eor2 = 0;
        for (int num : nums) {
            // 如果(num & rightOne) == 0，说明这些数在rightOne这一位上为0
            // 由于rightOne是a和b不同的位，所以nums中的数根据这一位可以分成两组
            // 一组包含a，另一组包含b
            // 在包含a的组中，a出现奇数次，其他数出现偶数次
            // 所以经过这一组的异或操作后，eor2的值就是a或者b
            if ((num & rightOne) == 0) {
                eor2 ^= num;
            }
        }

        // 4. 最后，通过eor1 ^ eor2得到另一个出现奇数次的数
        // 因为eor1 = a ^ b，已知eor2 = a（或者b），那么eor1 ^ eor2=(a ^ b)^a = b（或者a）
        return new int[] { eor2, eor1 ^ eor2 };
    }
}